有限オートマトン(finite automaton)
https://gyazo.com/07e501887ebb04e42ec5184c07e9ecc5
関連項目
説明
順序機械が出力する記号を1(yes) 0(no)の2種類に限定する
受け入れていい入力記号列が入力された時点では1、それ以外は0を出力するものとする
これは受け入れても良い記号列を認識する認識機械 recongnizerとして働く
このように認識機械としてみたときのムーア型順序機械のことを、有限オートマトン finite automaton FA もしくは 有限状態オートマトン finite state automaton FSA と呼ぶ
出力関数は明示する必要がなく、代わりに受理状態（最終状態）を明示することで定義できる
出力記号の有限集合 $ \Deltaは $ \Delta = \{0,1\}と固定されるので明示する必要はなくなる
言葉
1を出す状態へ到達させる入力文字列はこの機械に受理される accept という
1を出す状態は受理状態、もしくは最終状態という
定式化
$ M = (Q, \Sigma, \Delta, \delta, q_0, F) と表せる。
状態の有限集合$ Q
入力記号の有限集合 $ \Sigma
状態推移関数 state tranfer function $ \delta: (Q \times \Sigma) \longrightarrow Q
初期状態 $ q_0 \in Q
最終状態 $ F
状態遷移が決定的であることを強調してdeterministic finite automaton(決定的有限オートマトン)と呼ぶこともあるhttps://gyazo.com/9777b5d896031431d313bca938c5adfa
記法2 拡張状態推移関数 $ \hat\delta
上記の記法と同じことを式で表す方法がある
状態推移関数 $ \deltaは状態と「入力記号」を受け取るが、これを「入力記号列」を受け取るように拡張するのが拡張状態推移関数